package first.codeTop.alibaba;

/**
 * @ClassName LC34
 * @description:
 * @author: 荣燊
 * @create: 2021-10-19 14:49
 **/
public class LC34 {
    // 在排序数组中查找元素的第一个和最后一个位置,时间复杂度要求log(n)
    public static void main(String[] args) {
        int[] nums = {1, 2, 2, 3, 4, 6, 6, 8, 8, 9};
        int target = 6;
//        System.out.println(search(nums, target));
        System.out.println(binarySearch2(nums, target));
    }

    // 二分查找法
    public static int[] searchRange(int[] nums, int target) {
        int[] res = new int[2];
        int left = binarySearch1(nums, target);
        int right = binarySearch2(nums, target)-1;
        if (left <= right && right <= nums.length && nums[left] == target && nums[right] == target) {
            return new int[]{left, right};
        }
        return new int[]{-1, -1};
    }

    //查找左边界
    public static int binarySearch1(int[] nums, int target) {
        int l = 0;
        int r = nums.length-1;
        int ans = 0;
        while (l <= r) {
            int mid = (l+r) / 2;
            if (nums[mid] >= target) {
                r = mid - 1;
                ans = mid;
            } else {
                l = mid + 1;
            }
        }
        return ans;
    }

    //
    public static int binarySearch2(int[] nums, int target) {
        int l = 0;
        int r = nums.length-1;
        int ans = 0;
        while (l <= r) {
            int mid = (l+r) / 2;
            if (nums[mid] > target) {
                r = mid - 1;
                ans = mid;
            } else {
                l = mid + 1;
            }
        }
        return ans;
    }


    public static int search(int[] nums, int target) {
        int i = 0;
        int j = nums.length-1;
        int temp = 0;
        while (i <= j) {
            temp = (i+j) / 2;
            if (target == nums[temp]) {
                return temp;
            } else if (target > nums[temp]) {
                i = temp + 1;
            } else {
                j = temp - 1;
            }
        }
        return -1;
    }
}
